package airthmetic.exercise.backtrack;

public class _200_岛屿数量 {
    static int row;
    static int clos;
    static int[][] caculate = {{0,1},{0,-1},{-1,0},{1,0}};
    public static int numIslands(char[][] grid) {
        int count = 0;
        row = grid.length;
        if(row == 0){
            return count;
        }
        clos = grid[0].length;
        boolean[][] used = new boolean[row][clos];

        for(int i=0; i<row; i++){
            for(int j=0; j<clos; j++){
                if(grid[i][j] == '1' && !used[i][j]){
                    dfs(i,j,grid,used);
                    count++;
                }
            }
        }

        return count;
    }

    public static void dfs(int x, int y, char[][] grid, boolean[][] used){
        used[x][y] = true;

        for(int i=0; i<4; i++){
            int newX = x + caculate[i][0];
            int newY = y + caculate[i][1];

            // 当前索引在网格内，并且是陆地，并且没被选择过
            if(inGrid(newX,newY) && grid[newX][newY] == '1' && !used[newX][newY]){
                dfs(newX,newY,grid,used);
            }
        }
    }

    public static boolean inGrid(int x, int y){
        return x >=0 && x < row && y >=0 && y <clos;
    }


    public static void main(String[] args) {
        char[][] grid = {{'1','1','1','1','0'},{'1','1','0','1','0'},{'1','1','0','0','0'},{'0','0','0','0','0'}};
        System.out.println("岛屿的数量是：" + numIslands(grid));
    }
}
